package offer;

@FunctionalInterface
public interface BinaryGap {
    int binaryGap(int n);
}
class BinaryGapTest{
    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            BinaryGapImpl1 impl1 = new BinaryGapImpl1();
            System.out.print(i + " | " + impl1.binaryGap(i) +" | ");
            for (int i1 : BinaryGapImpl1.bitMap) {
                System.out.print(i1);
            }
            System.out.println();
        }
    }
}
class BinaryGapImpl1 implements BinaryGap{
    public static int[] bitMap;
    @Override
    public int binaryGap(int n) {
        bitMap = new int[32];
        if(n == 0){
            return 0;
        }
        getBitMap(bitMap, n);
        int pre = -1, cur = -1;
        int maxDistance = 0;
        for (int i = 0; i < 32; i++) {
            if(bitMap[i] == 1){
                pre = cur;
                cur = i;
            }
            if(pre != -1){
                int curDistance = cur - pre;
                maxDistance = curDistance > maxDistance ? curDistance: maxDistance;
            }
        }
        if(pre == -1){
            return 0;
        }else {
            return maxDistance;
        }
    }
    private void getBitMap(int[] bitMap, int n){
        int i = 0;
        while(n != 0){
            int x = n % 2;
            bitMap[i] = x;
            n = n / 2;
            i++;
        }
        return ;
    }
}

class BinaryGapImpl2 implements BinaryGap{
    @Override
    public int binaryGap(int n) {

        int pre = -1, cur = -1;
        int i = 0, maxDistance = 0;
        while(n != 0){
            int x = n % 2;
            n = n / 2;
            if(x == 1){
                pre = cur;
                cur = i;
            }
            if(pre != -1){
                int curDistance = cur - pre;
                maxDistance = curDistance > maxDistance ? curDistance: maxDistance;
            }
            i++;
        }
        if(pre == -1){
            return 0;
        }else {
            return maxDistance;
        }
    }
}
